/***************Program of All Shortest Path Algorithm******************/

import java.util.*;

class Graph
{
	int g[][];
	int v,e;
	
	void creategraph()
	{
		int a,b,w;
		Scanner kbd=new Scanner(System.in);
		System.out.println("enter number of vertices");
		v=kbd.nextInt();
		System.out.println("Enter number of edges");
		e=kbd.nextInt();
	
		g=new int[v+1][v+1];

		for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
		g[i][j]=32767;

		for(int i=1;i<=v;i++)
 		g[i][i]=0;

		for(int i=1;i<=e;i++)
		{
			System.out.println("Enter Edge information");
			a=kbd.nextInt();
			b=kbd.nextInt();
			System.out.println("Enter Weight");
			w=kbd.nextInt();
			g[a][b]=w;
			}
	}

	void allpair()
	{
		for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
		g[i][j]=Math.min(g[i][j],g[i][k]+g[k][j]);
		
		System.out.println("From \t\t to");
		for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
		System.out.println(i+ " \t\t\t\t " +j+ "=" +g[i][j]);
	}
}
 public class AllPair
{

	public static void main(String args[])
	{
		Graph g=new Graph();
		g.creategraph();
		g.allpair();
	}
}


/****************** output******************************
C:\Program Files\Java\jdk1.7.0\bin>java AllPair
enter number of vertices
5
Enetr number of edges
4
Enter Edge information
2
3
Enter Weight
1
Enter Edge information
2
3
Enter Weight
2
Enter Edge information
3
1
Enter Weight
1
Enter Edge information
2
1
Enter Weight
3
From             to
1                                1=0
1                                2=32767
1                                3=32767
1                                4=32767
1                                5=32767
2                                1=3
2                                2=0
2                                3=2
2                                4=32767
2                                5=32767
3                                1=1
3                                2=32767
3                                3=0
3                                4=32767
3                                5=32767
4                                1=32767
4                                2=32767
4                                3=32767
4                                4=0
4                                5=32767
5                                1=32767
5                                2=32767
5                                3=32767
5                                4=32767
5                                5=0


*/